package com.singzi.leetcode.jianzhiOffer2;

import java.util.Arrays;

public class T0017 {
}
class Solution {
    public String minWindow(String s, String t) {
        if(t.length() > s.length()) return "";
        int left = 0, right = t.length();
        int []letters = new int['z' - 'A'+1];
        for(int i = 0; i <  t.length();i++){
            letters[s.charAt(i) - 'A']++;
            letters[t.charAt(i) - 'A']--;
        }
        if(isTargetNums(letters)) return s.substring(0, t.length());
        int min = Integer.MAX_VALUE;
        int start = 0;
        while (right <= s.length()){
            while (letters[s.charAt(left) - 'A'] >=0 && isTargetNums(letters)){
                if(right - left < min){
                    min = right - left;
                    start = left;
                }
                letters[s.charAt(left) - 'A']--;
                left++;
            }
            if(right < s.length()){
                letters[s.charAt(right) - 'A']++;
            }
            right++;
        }
        return min < Integer.MAX_VALUE?s.substring(start, start+min):"";

    }

    private boolean isTargetNums(int[] letters) {
        for(int letter:letters){
            if(letter < 0) return false;
        }
        return true;
    }
}